DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.77

A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs

Authors: Guozhen Rong, Yongjie Yang, and Wenjun Li

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We study the partial search order problem (PSOP) proposed recently by Scheffler [WG 2022]. Given a graph G together with a partial order on the set of vertices of G, this problem determines if there is an 𝒮-ordering that is consistent with the given partial order, where 𝒮 is a graph search paradigm like BFS, DFS, etc. This problem naturally generalizes the end-vertex problem which has received much attention over the past few years. It also generalizes the so-called ℱ-tree recognition problem which has just been studied in the literature recently. Our main contribution is a polynomial-time dynamic programming algorithm for the PSOP of the maximum cardinality search (MCS) restricted to chordal graphs. This resolves one of the most intriguing open questions left in the work of Scheffler [WG 2022]. To obtain our result, we propose the notion of layer structure and study numerous related structural properties which might be of independent interest.

Cite as

Guozhen Rong, Yongjie Yang, and Wenjun Li. A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rong_et_al:LIPIcs.MFCS.2023.77,
  author =	{Rong, Guozhen and Yang, Yongjie and Li, Wenjun},
  title =	{{A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{77:1--77:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.77},
  URN =		{urn:nbn:de:0030-drops-186118},
  doi =		{10.4230/LIPIcs.MFCS.2023.77},
  annote =	{Keywords: partial search order, maximum cardinality search, chordal graphs, clique graphs, dynamic programming}
}

Search Results

Documents authored by Li, Wenjun

A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message